package sword.chapter2Array;

/**
 * 二维子矩阵的和
 * 输入一个二维矩阵，如何计算给定左上角坐标和右下角坐标的子矩阵数字之和？对同一个二维矩阵，计算子矩阵数字之和的函数可能输入不同的坐标而被反复调用多次。
 * 例如输入图2.1中的二维矩阵，以及左上角坐标为(2, 1)和右下角坐标为(4, 3)，该函数输出8。
 *
 * 1. sum[i+1[j+1] = Snums[i][j]  矩阵上边构建了一行、左边构建一列为0的数组
 * 2. S：A-B-C+D = 待求子矩阵之和
 * 3. 2中的下标进行替换
 * @author K
 * @date 2021/11/4 12:16
 */
public class S13NumMatrix {
    private static int[][] sum;

    public static void main(String[] args) {
        int[] row1 = new int[]{1, 2, 3, 4, 5};
        int[] row2 = new int[]{1, 2, 3, 4, 5};
        int[] row3 = new int[]{1, 2, 3, 4, 5};
        int[] row4 = new int[]{1, 2, 3, 4, 5};
        int[] row5 = new int[]{1, 2, 3, 4, 5};
        int[][] nums = new int[5][5];
        nums[0] = row1;
        nums[1] = row2;
        nums[2] = row3;
        nums[3] = row4;
        nums[4] = row5;
        s13(nums);
        int result = result(sum, 1, 1, 2, 2);
        System.out.println();
    }

    public static void s13(int[][] nums) {
        sum = new int[nums.length + 1][nums[0].length + 1];
        for (int i = 0; i < nums.length; i++) {
            int rowSum = 0;
            for (int j = 0; j < nums[0].length; j++) {
                rowSum += nums[i][j];
                sum[i + 1][j + 1] = sum[i][j + 1] + rowSum;
            }
        }
    }

    public static int result(int[][] sum, int row1, int col1, int row2, int col2) {
        // sum[row1][col2 + 1] 与上面求和中第二个for中的sum[i][j+1]保持一致
        return sum[row2 + 1][col2 + 1] - sum[row1][col2 + 1] - sum[row2 + 1][col1] + sum[row1][col1];
    }
}
